package algorithm_study.leecode;

public class isExist {
    public boolean exist(char[][] board, String word) {
        char start=word.charAt(0);
        char[]data= word.toCharArray();
        int n=board.length;
        int m=board[0].length;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j]==start){
                    if(find(i,j,board,1,data,n,m,' ')){
                        return true;
                    }
                }
            }
        }
        return false;

    }
    public boolean find(int i,int j,char[][]board,int index,char[] data,int n,int m,char flag){
        //上
        if(i-1>=0&&flag!='w'){
            if(board[i-1][j]==data[index]){
                flag='s';
                if(index==data.length-1){
                    return true;
                }
                if(find(i-1,j,board,index+1,data,n,m,flag)){
                    return true;
                }
            }
        }
        //下
        if(i+1<=n-1&&flag!='s'){
            if(board[i+1][j]==data[index]){
                flag='w';
                if(index==data.length-1){
                    return true;
                }
                if(find(i+1,j,board,index+1,data,n,m,flag)){
                    return true;
                }
            }
        }
        //左
        if(j-1>=0&&flag!='a'){
            if(board[i][j-1]==data[index]){
                flag='d';
                if(index==data.length-1){
                    return true;
                }
                if(find(i,j-1,board,index+1,data,n,m,flag)){
                    return true;
                }
            }
        }
        //右
        if(j+1<=m-1&&flag!='d'){
            if(board[i][j+1]==data[index]){
                flag='a';
                if(index==data.length-1){
                    return true;
                }
                if(find(i,j+1,board,index+1,data,n,m,flag)){
                    return true;
                }
            }
        }
        return false;
    }
}
